␈↓␈↓↓␈↓ αOLISP - a high-level mathematical language for data structures.  ␈↓ 

␈↓Just␈α⊃as␈α⊃it␈α⊃is␈α⊃unnecessary␈α⊂to␈α⊃learn␈α⊃machine␈α⊃language␈α⊃to␈α⊂study␈α⊃numerical␈α⊃algorithms,␈α⊃it␈α⊃is␈α⊂also
␈↓unnecessary␈α∞to␈α∞learn␈α∂machine␈α∞language␈α∞to␈α∂understand␈α∞non-numerical␈α∞processes.␈α∂ The␈α∞distinction
␈↓we␈α⊂are␈α⊂making␈α⊂is␈α⊃between␈α⊂data-structures␈α⊂and␈α⊂storage␈α⊃structures.␈α⊂ That␈α⊂is,␈α⊂data␈α⊃structures␈α⊂are
␈↓independent␈α
of␈α
␈↓¬how␈↓␈α
they␈α
are␈α
implemented␈α
on␈α
a␈α
machine.␈α
 Data␈α
structures␈α
are␈α
representations␈αof
␈↓information␈α∃chosen␈α∃to␈α∃exhibit␈α∃certain␈α∃ordering␈α∃and␈α∃accessibility␈α∃relation-ship␈α∃between␈α∀data
␈↓structures.␈α
 Certainly␈αin␈α
the␈αreal␈α
world␈αyou␈α
cannot␈α
ignore␈αstorage␈α
structures␈αwhen␈α
you␈αare␈α
deciding
␈↓upon␈α⊗the␈α⊗data␈α⊗structures␈α∃which␈α⊗will␈α⊗encode␈α⊗your␈α∃problem,␈α⊗but␈α⊗the␈α⊗interesting␈α⊗aspects␈α∃of
␈↓representation␈α⊂of␈α⊂information␈α⊂can␈α⊂be␈α⊂discussed␈α⊂at␈α⊂the␈α⊂level␈α⊂of␈α⊂data␈α⊂structures␈α⊂with␈α⊂no␈α⊂loss␈α∂of
␈↓generality.␈α∞ The␈α∞mapping␈α∞of␈α∞data␈α∞structures␈α
to␈α∞storage␈α∞structures␈α∞is␈α∞machine␈α∞dependent␈α
anyway,
␈↓and␈α
consists␈αof␈α
bit-pushing,␈α
trickery␈αand␈α
black␈α
magic.␈α A␈α
very␈α
crucial␈αproblem␈α
in␈α
data␈αstructures
␈↓and␈α
algorithms␈α
is␈α
the␈αinterplay␈α
between␈α
the␈α
representation␈α
and␈αthe␈α
algorithm:␈α
 if␈α
you␈α
pick␈αa␈α
frugal
␈↓representation␈α∞prhaps␈α∞your␈α∂accessing␈α∞algorithms␈α∞become␈α∞more␈α∂time␈α∞consuming␈α∞or␈α∂the␈α∞algorithm
␈↓become␈α
less␈α
general.␈α
 We␈α
will␈α
study␈α
this␈α
interrelation␈α
carefully␈α
in␈α
this␈α
course.

␈↓If␈α∂you␈α∂take␈α∂a␈α∂course␈α∂in␈α∂elementary␈α⊂number␈α∂theory␈α∂or␈α∂better␈α∂yet␈α∂recursive␈α∂function␈α⊂theory,␈α∂you
␈↓would␈α∩begin␈α∩with␈α∩a␈α∩precise␈α∩description␈α∩of␈α∩the␈α∩domain␈α∩of␈α∩interest␈α∩(the␈α∪non-negative␈α∩integers
␈↓perhaps,␈α
or␈α
0␈α∞and␈α
the␈α
successor␈α
function)␈α∞and␈α
then␈α
describe␈α
the␈α∞class␈α
of␈α
functions␈α∞or␈α
operations
␈↓which␈α
will␈α
be␈α
allowed␈α
in␈α
the␈α
developing␈α
theory.␈α
We␈α
will␈α
do␈α
the␈α
same.

␈↓Our␈α∂primitive␈α∂domain␈α∂consists␈α∞of␈α∂objects␈α∂called␈α∂atoms␈α∞or␈α∂atomic␈α∂symbols.␈α∂ In␈α∂computer␈α∞science
␈↓terminolgy␈α
they␈α
are␈α
either␈α
identifiers␈α
or␈α
numbers;␈α
i.e.


␈↓<atom>␈↓ β_:: = <identifier>|<number>
␈↓<identifier>␈↓ β_:: = <letter>|<identifier><letter>|<identifier><digit>
␈↓<number>␈↓ β_:: = <digit>|<number><digit>
␈↓<letter>␈↓ β_:: =␈↓α A |B |C ...| Z␈↓
␈↓<digit>␈↓ β_:: = ␈↓α0 |1 |2 ... |9␈↓


␈↓For example:␈↓ ∧λatoms␈↓ ¬xnot atoms
␈↓␈↓α␈↓ ∧λABC123␈↓ ¬x2a
␈↓α␈↓ ∧λ12␈↓ ¬xa
␈↓α␈↓ ∧λA4D6␈↓ ¬x$$g
␈↓α␈↓ ∧λNIL␈↓ ¬xABD.
␈↓α␈↓ ∧λT␈↓ ¬x(A . B)

␈↓Using␈α
an␈α
operator␈αto␈α
be␈α
described␈α
later,␈αwe␈α
are␈α
able␈α
to␈αenlarge␈α
on␈α
this␈α
primitive␈αdomain␈α
obtaining
␈↓the␈α∩domain␈α∩of␈α∩interest␈α∩for␈α∩LISP␈α∩functions,␈α∪that␈α∩is␈α∩the␈α∩class␈α∩of␈α∩␈↓¬symbolic␈α∩expressions␈↓␈α∪or␈α∩␈↓¬S-
␈↓¬expressions␈↓␈αor␈αalso␈αcalled␈α␈↓¬S-exprs␈↓.␈α S-exprs␈αinclude␈αas␈αa␈αproper␈αsubset␈αthe␈αatoms,␈αbut␈αS-exprs␈α
can
␈↓be␈α∂constructed␈α⊂of␈α∂other␈α⊂S-exprs␈α∂as␈α∂follows:␈α⊂ a␈α∂left-paren␈α⊂followed␈α∂by␈α∂an␈α⊂S-expr,␈α∂followed␈α⊂by␈α∂a
␈↓period,␈αfollowed␈α
by␈αan␈αS-expr,␈α
followed␈αby␈α
a␈αperiod,␈αfollowed␈α
by␈αan␈αS-expr,␈α
followed␈αby␈α
a␈αright-
␈↓paren␈α
is␈α
also␈α
an␈α
S-expr.␈α
 To␈α
make␈α
everyone␈α
happy␈α
here's␈α
a␈α
BNF␈α
definition␈α
of␈α
S-expr

␈↓␈↓ ∧?<sexpr> :: = <atom>|␈↓α(␈↓<sexpr> . <sexpr>␈↓α) |( )␈↓ 



␈↓We␈α
added␈α
"␈↓α(␈α
)␈↓"␈α
as␈α
an␈α
S-expr␈α
for␈α
a␈α
reason␈α
which␈α
will␈α
become␈α
clear␈α
later.
␈↓Examples:␈↓ ∧λS-exprs␈↓ ε8not S-exprs
␈↓α␈↓ ∧λA␈↓ ε8A . B
␈↓α␈↓ ∧λ(A . B)␈↓ ε8(A . B . C)
␈↓α␈↓ ∧λ(((A.B) .C) . (A.B))␈↓ ε8((A . B)))



␈↓Non-atomic␈α
sexprs␈α
are␈α
also␈α
called␈α
␈↓¬dotted-pairs␈↓.␈α
 S-exprs␈α
have␈α
a␈α
natural␈α
interpretation␈α
as␈αbinary
␈↓trees.␈α⊂ A␈α⊂binary␈α⊂tree␈α⊂is␈α⊂a␈α⊂branching␈α⊂structure␈α⊂consisting␈α⊂of␈α⊂a␈α⊂single␈α⊂root␈α⊂node␈α⊂and␈α⊂perhaps␈α∂a
␈↓collection␈α∞of␈α∞terminal␈α∂and␈α∞non-terminal␈α∞nodes.␈α∞ From␈α∂non-terminal␈α∞nodes␈α∞we␈α∞sprout␈α∂exactly␈α∞two
␈↓branches;␈α∞no␈α∞branches␈α∞are␈α∂grown␈α∞from␈α∞the␈α∞terminal␈α∞nodes.␈α∂ And␈α∞most␈α∞important:␈α∞ there␈α∂are␈α∞no
␈↓intersecting␈α⊂branches.␈α∂ We␈α⊂will␈α∂alk␈α⊂about␈α∂more␈α⊂general␈α∂structures␈α⊂later␈α∂(called␈α⊂list-structures␈α∂or
␈↓directed␈α
graphs).



␈↓Here␈α
are␈α
some␈α
binary␈α
tres:

␈↓α                                        .                 
␈↓α                                        A
␈↓α                                                        A  


␈↓α        1  2                                            B      NIL


␈↓α                A       D     E



␈↓α                  B  C


␈↓α␈↓Perhaps␈αyou␈αcan␈αsee␈αhow␈αto␈αinterpret␈αS-exprs␈αnow.␈α The␈αatoms␈αare␈αinterpreted␈αas␈αterminal␈αnodes;
␈↓and␈αsince␈αnon-atomic␈αS-exprs␈αalways␈αhave␈αtwo␈αbranches␈α(oops,␈αtwo␈αsub-expressions)␈αwe␈αcan␈αwrite
␈↓the␈α
first␈αsub-expression␈α
as␈αthe␈α
left␈αbranch␈α
of␈αa␈α
binary␈αtree␈α
and␈αthe␈α
second␈αsub-expression␈α
as␈αthe
␈↓right␈α
branch.




␈↓For␈α
example:
␈↓α        (A . B)                         (A . (B . C))



␈↓α                                       A   

␈↓α         A  B                            
␈↓α                                        B    C








␈↓α        ((A . B) . C)                   (A . (B . NIL))





␈↓α                C                       A  


␈↓α     A      B                               B      NIL


␈↓α␈↓Other␈α∃representations␈α∃of␈α∀binary␈α∃trees␈α∃which␈α∀will␈α∃be␈α∃more␈α∀suggestive␈α∃when␈α∃we␈α∃talk␈α∀about
␈↓implementation␈α
of␈α
LISP␈α
are:␈α
␈↓α

␈↓α(A . (B . C))



␈↓α ≡        A             ≡                                 ≡ 

␈↓α                                  A            B     C 





␈↓α              B    C  




␈↓α                                                                   B        C


␈↓α␈↓¬Note␈α
that␈α
the␈α
translation␈α
process␈α
is␈α
inherently␈α
recursive.␈α
 ␈↓



␈↓So␈α⊃much␈α⊃for␈α⊃the␈α⊃domain␈α⊃of␈α⊃objects;␈α⊃ what␈α⊃we␈α⊃need␈α⊃now␈α⊃are␈α⊃some␈α⊃functions␈α⊃or␈α⊃operators␈α⊂to
␈↓perform␈α∞oprations␈α∞on␈α∞the␈α∞domain.␈α∞ First␈α∞such␈α∞function␈α∞is␈α∞the␈α∞␈↓αcons␈↓␈α∞(construct)␈α∞function␈α∞wwich␈α
is
␈↓used␈α
to␈αgenerate␈α
s-exprs␈αfrom␈α
less␈α
complicated␈αs-exprs.␈α
 ␈↓αcons␈↓␈αis␈α
a␈α
total␈αfunction,␈α
that␈αis␈α
it␈αis␈α
defined
␈↓for␈α∩all␈α∩sexpr␈α∪arguments.␈α∩It␈α∩is␈α∪a␈α∩function␈α∩of␈α∩two␈α∪arguments␈α∩and␈α∩has␈α∪as␈α∩value␈α∩a␈α∪new␈α∩sexpr
␈↓interpreted␈α∂as␈α∞a␈α∂binary␈α∞tree␈α∂with␈α∞left␈α∂branch␈α∞as␈α∂the␈α∞first␈α∂argument␈α∞and␈α∂with␈α∞right␈α∂branch,␈α∞the
␈↓second␈α
argument.␈α
 For␈α
example:
␈↓␈↓ ¬Z␈↓αcons[A; B] = (A . B)

␈↓α␈↓ ¬≤cons[(A . B); C] = ((A . B) .C)



␈↓We␈αhave␈αtwo␈αfunctions␈α
for␈αtraversing␈αbinary␈αtrees.␈α They␈α
are␈αboth␈αpartial␈αfunctions;␈αthat␈α
is␈αthey
␈↓are␈α∞(unary)␈α∞functions␈α
which␈α∞are␈α∞undefined␈α∞for␈α
atomic␈α∞arguments.␈α∞ ␈↓αcar␈↓␈α
returns␈α∞as␈α∞value␈α∞the␈α
first
␈↓subexpression␈α∞of␈α∞its␈α∞(composite)␈α
argument;␈α∞␈↓αcdr␈↓␈α∞(pronounced␈α∞could-er)␈α
returns␈α∞as␈α∞vlue␈α∞the␈α
second
␈↓sub-expression␈α
of␈α
its␈α
argument.␈α
 For␈α
example:


␈↓␈↓ αx␈↓αcar[(A . B)] = A␈↓ ¬(car[A] ␈↓is undefined.
␈↓␈↓ αx␈↓αcdr[(A . B)] = B␈↓ ¬(cdr[A(A . (B . C))] = (B . C)
␈↓α␈↓ αx␈↓ ∧acar[((A . B) . C)] = (A . B)


␈↓As␈α
with␈α
most␈α
mathematical␈α
theories,␈α
we␈α
will␈α
allow␈α
functional␈α
composition.
␈↓α␈↓ ∧≠car[cdr[(A . (B . C))]] = B = cdr[cdr[(A . (C . B))]]
␈↓α␈↓ ∧]car[cons[x;y]] = x     cdr[cons[x;y]] = y .

␈↓Notice␈α
that␈αin␈α
the␈α
last␈αtwo␈α
examples␈αwe␈α
have␈α
introduced␈αvariables␈α
(over␈αS-exprs).␈α
 In␈α
the␈αsequel
␈↓lower-case␈α
letters␈α
(or␈α
lower-case␈αidentifiers)␈α
will␈α
be␈α
used␈α
freely␈αas␈α
(sexpr)␈α
variables.␈α
 So␈αfor␈α
example



␈↓␈↓αY␈↓␈αis␈αan␈αatom;␈α␈↓αx␈↓␈αis␈αa␈αvariable␈αThe␈αcomposition␈αof␈αmany␈α␈↓αcar␈↓␈αand␈α␈↓αcdr␈↓␈αfunctions␈αoccurs␈αso␈αfrequently
␈↓that␈α
an␈α
abbreviation␈α
has␈α
been␈α
developed.


␈↓For example:
␈↓α␈↓ ¬Xcadr[x] ≡ car[cdr[x]]
␈↓α␈↓ ¬2caddr[x] ≡ car[cdr[cdr[x]]]
␈↓α␈↓ ¬Xcdar[x] ≡ cdr[car[x]]

␈↓These␈αcompositions␈αare␈αalso␈αcalled␈α"␈↓αcar-cdr␈↓"␈αchains,␈αand␈αare␈αuseful␈αin␈αtraversing␈αbinary␈αtrees.␈α We
␈↓cannot␈α∩generate␈α∩a␈α∩very␈α∩exciting␈α∩theory␈α∩based␈α∩simply␈α∩on␈α∩␈↓αcar,␈α∩cdr,␈↓␈α∩and␈α∩␈↓αcons␈α∩␈↓␈α∩with␈α∩functional
␈↓composition.␈α∂Before␈α∞we␈α∂can␈α∞write␈α∂reasonably␈α∞interesting␈α∂algorithms␈α∞we␈α∂must␈α∞have␈α∂some␈α∂way␈α∞of
␈↓performing␈α⊂conditional␈α⊂actions;␈α⊂an␈α⊃IF-THEN-ELSE␈α⊂facility␈α⊂if␈α⊂you␈α⊃wish.␈α⊂ To␈α⊂do␈α⊂this␈α⊃we␈α⊂need
␈↓predicates:␈α
 functions␈α
returning␈α∞a␈α
value␈α
representing␈α
truth␈α∞or␈α
falsity.␈α
 Since␈α
our␈α∞functions␈α
return
␈↓Sexprs␈α
as␈α∞values␈α
we␈α
must␈α∞represent␈α
truth␈α
and␈α∞falsity␈α
as␈α
Sexprs.␈α∞ We␈α
will␈α
take␈α∞the␈α
atoms␈α∞␈↓αT␈↓␈α
and
␈↓␈↓αNIL␈↓␈α
to␈α
represent␈α
true␈α∞and␈α
false,␈α
respectively.␈α
 Now␈α
two␈α∞predicates.␈α
The␈α
first␈α
is␈α
a␈α∞total␈α
predicate
␈↓named␈α␈↓αatom␈↓.␈α
 It␈αis␈α
a␈αpredicate␈αof␈α
one␈αargument␈α
returning,␈α␈↓αT␈↓␈αor␈α
␈↓αNIL␈↓␈αdepending␈α
on␈αwhether␈αor␈α
not
␈↓that␈α
argument␈α
is␈α
atomic.
␈↓α␈↓ ¬4atom[A] ≡ atom[NIL] = T
␈↓α␈↓ ∧Watom[atom[A]] = T = atom[atom[(A . B)]]

␈↓The␈αsecond␈αprimtive␈αpredicate␈αis␈αnamed␈α␈↓αeq␈↓.␈α It␈αis␈αa␈αbinary␈αpredicate␈αdefined␈αonly␈αif␈αits␈αarguments
␈↓are␈α
both␈α
atomic.␈α
 It␈α
returns␈α
␈↓αT␈↓␈α
if␈α
the␈α
arguments␈α
are␈α
the␈α
same␈α
atom;␈α
it␈α
returns␈α
␈↓αNIL␈↓␈α
otherwise.

␈↓α␈↓ ∧Geq [A;A] = T                   eq [A;B] = NIL
␈↓α␈↓ ∧eq [(A . B); A] ␈↓ is undefined, as is  ␈↓αeq [(A . B);(A . B)]
␈↓α␈↓ ¬3eq [eq [A;B];eq [C;D]] = T

␈↓The␈α
IF-THEN-ELSE␈α
operation␈α
in␈α
LISP␈α
is␈α
called␈α
the␈α
condition␈α
expression.␈α
 It␈α
is␈α
written:
␈↓α␈↓ ¬∪[p␈↓β1␈↓α → e␈↓β1␈↓α; p␈↓β2␈↓α → e␈↓β2␈↓α  ... ; p␈↓βn␈↓α  → e␈↓βn␈↓α]

␈↓The␈α∞meaning␈α∞(or␈α∞semantics)␈α
of␈α∞conditionals␈α∞is:␈α∞ Each␈α
␈↓αp␈↓βi␈↓␈α∞is␈α∞a␈α∞predicate;␈α
each␈α∞␈↓αe␈↓βi␈↓␈α∞is␈α∞an␈α
expression.
␈↓We␈αevaluate␈α
the␈α␈↓αp␈↓βi␈↓␈α's␈α
from␈αleft␈α
to␈αright,␈αfinding␈α
the␈αfirst␈α
which␈αreturns␈αvalue␈α
␈↓αT␈↓.␈α When␈α
we␈αfind
␈↓such␈α
a␈α
␈↓αp␈↓βi␈↓␈α
,␈αwe␈α
evaluate␈α
the␈α
corresponding␈α␈↓αe␈↓βi␈↓.␈α
 The␈α
value␈α
of␈αthe␈α
conditional␈α
expression␈α
the␈αvalue
␈↓returned␈α∂by␈α⊂␈↓αe␈↓β␈↓;␈α∂if␈α∂none␈α⊂of␈α∂the␈α⊂␈↓αp␈↓βi␈↓'s␈α∂are␈α∂true␈α⊂then␈α∂the␈α∂conditional␈α⊂expression␈α∂is␈α⊂undefined.␈α∂ The
␈↓conditional␈α
expression␈α
is␈α
also␈α
undefined␈α
if␈α
we␈α
come␈α
across␈α
a␈α
␈↓αp␈↓βi␈↓␈α
which␈α
is␈α
undefined.
␈↓Examples:

␈↓α␈↓ ∧e[atom [A] → B; eq [A;(A . B)] → C] = B
␈↓α␈↓ ∧-[eq [A;(A . B)] → C; atom [A] → B] is undefined
␈↓α␈↓ α⎇[atom [(A . B)] → B; eq [A ; B] → C; eq [car[(A . B)]; cdr[(B . A)]] → E] = E

␈↓In␈αapplications␈αof␈αconditional␈αexpressions␈αit␈αis␈αoften␈αconvenient␈αto␈αbe␈αassured␈αthat␈αthe␈αconditional



␈↓always␈α
is␈α
defined.␈α
 To␈α
make␈αsure␈α
that␈α
at␈α
least␈α
one␈αof␈α
the␈α
␈↓αp␈↓βi␈↓'s␈α
is␈α
true␈αwe␈α
can␈α
pick␈α
a␈α
predicate␈αfor␈α
␈↓αp␈↓βn␈↓,
␈↓(the␈α
last␈α∞predicate␈α
in␈α
the␈α∞conditional)␈α
which␈α∞is␈α
always␈α
true.␈α∞ You␈α
can␈α
think␈α∞of␈α
lots␈α∞of␈α
predicates
␈↓which␈α
are␈α
always␈α
true␈α(␈α
for␈α
example,␈α
␈↓αeq␈α[1;1]␈↓␈α
).␈α
 A␈α
natural␈αpredicate␈α
is␈α
the␈α
constant␈α
predicate,␈α␈↓αT␈↓.
␈↓Thus:

␈↓α␈↓ ¬f[p␈↓β1␈↓α  → e␈↓β1␈↓α; T → e␈↓β2␈↓α]

␈↓can␈α
be␈α
read:␈α
 If␈α
␈↓αp␈↓β1␈↓␈α
 is␈α
true␈α
then␈α
 ␈↓αe␈↓β1␈↓␈α
 else␈α
␈↓αe␈↓β2␈↓.␈α
 (or␈α
otherwise␈α
␈↓αe␈↓β2␈↓)

␈↓A␈αword␈αto␈αthe␈αwise.␈α It␈αdoesn't␈αseem␈αlike␈αyou␈αcan␈αdo␈αmuch␈αdamage␈αwith␈αsuch␈αa␈αlimited␈αcollection
␈↓of␈αoperations.␈α ␈↓¬Do␈αnot␈αbe␈αdeceived!␈↓␈α In␈αelementary␈αnumber␈αtheory␈αall␈αyou␈αhave␈αis␈αzero␈αand␈αsome
␈↓simple␈α
functions,␈α
and␈α
elementary␈α
number␈α
theory␈α
is␈α
far␈α
from␈α
elementary.

␈↓For␈αexample:␈αour␈αpredicate␈α␈↓αeq␈↓␈αis␈αdefined␈αonly␈αfor␈αatomic␈αarguments.␈α We␈αwould␈αlike␈αto␈αbe␈αable␈αto
␈↓test␈αfor␈αequality␈αof␈α
arbitrary␈αsexprs.␈α For␈αexample,␈α
we␈αwould␈αlike␈αto␈α
define␈αa␈αpredicate,␈α␈↓αequal␈↓,␈α
such
␈↓that:

␈↓α␈↓ ∧Zequal [(A . B);(A . B)] = T = equal [A,A]
␈↓α␈↓ ¬≥equal [(A . B);(B . A)] = NIL
␈↓α␈↓ ∧nequal [(A . (B . C));(A . (B . C))] = T


␈↓Here's␈α
an␈α
intuitive␈α
description␈α
of␈α
such␈α
a␈α
function␈α
(predicate␈α
named␈α
␈↓αequal␈↓).

␈↓1.␈α if␈αboth␈αarguments␈αare␈αatomic␈αthen␈αsee␈αwhat␈α␈↓αeq␈↓␈αsays␈αabout␈αthem␈α(are␈αthey␈α"␈↓αeq␈↓").␈α We␈αmake␈αsure
␈↓that␈α
they␈α
are␈α
both␈α
atomic␈α
by␈α
using␈α
␈↓αatom␈↓␈α
and␈α
a␈α
conditional␈α
expression.

␈↓2.␈α
 If␈α
one␈α
is␈α
atomic␈α
and␈α
the␈α
other␈α
is␈α
not␈α
they␈α
can't␈α
be␈α
equal␈α
s-exprs.

␈↓3.␈α
 Otherwise␈α
both␈α
are␈α
non-atomic␈α
sexprs.␈α
 Both␈α
have␈α
two␈α
sub-expressions.

␈↓Look␈α∞at␈α∂both␈α∞first␈α∞subexpressions.␈α∂ If␈α∞the␈α∞first␈α∂sub-expressions␈α∞are␈α∞not␈α∂equal␈α∞then␈α∂certainly␈α∞the
␈↓initial␈α
expressions␈α
cannot␈αhope␈α
to␈α
be␈α
equal.␈α However,␈α
if␈α
the␈αfirst␈α
subexpressions␈α
are␈α
equal␈αthen
␈↓the␈αquestion␈αof␈αwhether␈αor␈αnot␈αthe␈αinitial␈αexpressions␈αare␈αequal␈αdepends␈αon␈αthe␈αequality␈α(␈αor␈αnon-
␈↓equality)␈α
of␈α
the␈α
second␈α
subexpressions.␈α
 Thus␈α
the␈α
following␈α
definition:

␈↓αequal[x,y] <=␈↓ βx[atom[x] → [atom[y] → eq [x;y]
␈↓α␈↓ βx␈↓ ¬( T→ NIL];
␈↓α␈↓ βx atom[y] → NIL;
␈↓α␈↓ βx equal [car[x];car[y]] → equal[cdr[x];cdr[y]];
␈↓α␈↓ βx T → NIL]


␈↓␈↓↓␈↓ ¬yList Notation ␈↓ 



␈↓In␈αmany␈αapplications␈αof␈αLISP␈αit␈αwill␈αbe␈αvery␈αconvenient␈αto␈αrepresent␈αsequences.␈α E.g.␈α␈↓α(x␈↓β1␈↓α,␈α
x␈↓β2␈↓α,␈αx␈↓β3␈↓α)␈↓.
␈↓We␈αwill␈αallow␈αsequences␈αto␈αhave␈αsub-sequences␈α(to␈αan␈αarbitrary␈αdepth)␈αe.g.␈α␈↓α(A,(B,C),D,(E,B))␈↓.␈α The
␈↓obvious␈α∞question␈α∞is␈α∞how␈α∞to␈α∞represent␈α∞sequences␈α∞as␈α∞Sexprs.␈α∞ Since␈α∞sequences␈α∞can␈α∞be␈α∞of␈α∞arbitrary
␈↓length␈α∞any␈α∞representation␈α∞must␈α∞include␈α∞an␈α∞unambiguous␈α∞way␈α∞of␈α∞determining␈α∞the␈α∞end␈α∞of␈α∞such␈α
a
␈↓sequence.␈α
 The␈α
choice␈α
we␈α
make␈α
is␈α
represented␈α
graphically␈α
as␈α
follows:␈α
␈↓α


␈↓α                                                     ≡ (X  . (Y  . (Z  . NIL)))

␈↓αX               Y               Z      NIL


␈↓Note␈α
that␈α
we␈α
can␈α
determine␈α
the␈α
end␈α
of␈α
the␈α
sequence␈α
using␈α
the␈α
predicate:
␈↓α␈↓ ∧/endofseq[x] = [atom[x] → eq[x,NIL]; T → NIL]

␈↓That␈αis␈αthe␈αright-hand␈αbranch␈αin␈αany␈αbinary␈αtree␈αrepresenting␈αa␈αsequence␈αwill␈αalways␈αpoint␈αto␈α
the
␈↓rest␈αof␈αthe␈αsequence␈αor␈αwill␈αbe␈α
the␈αatom␈α␈↓αNIL␈↓.␈α It␈αis␈αnot␈αby␈α
accident␈αthat␈αthe␈αatom␈α␈↓αNIL␈↓␈αis␈αused␈α
for
␈↓falsity␈α∪and␈α∪the␈α∪termination␈α∪symbol␈α∪for␈α∩sequences.␈α∪ You␈α∪should␈α∪become␈α∪fluent␈α∪in␈α∩translating
␈↓between␈α
sexpr-notation␈α
and␈α
sequence␈α
notation.

␈↓In␈αstandord␈αComputer␈αScience␈αterminology␈αsequences␈αare␈αcalled␈αlists,␈αthus␈αwe␈αwill␈αrefer␈αusually␈αto
␈↓list-notation␈αlist␈αterminator,␈αetc.␈α You␈αshould␈αalso␈αbecome␈αfluent␈αin␈αapplying␈αour␈αbasic␈αfunctions␈αto
␈↓lists␈α
without␈α
having␈α
to␈α
translate␈α
back␈α
to␈α
sexpr-notation.

␈↓A␈α⊗final␈α⊗point:␈α⊗ what␈α∃about␈α⊗the␈α⊗empty␈α⊗sequence␈α⊗or␈α∃empty␈α⊗list?␈α⊗Looking␈α⊗at␈α⊗the␈α∃graphical
␈↓interpretation␈αof␈αa␈αsequence␈αit␈αappears␈αnatural␈αto␈αtake␈α␈↓αNIL␈↓␈αas␈αthe␈αempty␈αlist␈αsince␈αafter␈αyou␈αhave
␈↓removed␈α
all␈α
the␈α
elements␈αfrom␈α
the␈α
list,␈α
␈↓αNIL␈↓,␈α
the␈αlist␈α
terminator␈α
is␈α
all␈αthat␈α
is␈α
left.␈α
 Also␈α
from␈αthe
␈↓standpoint␈α∞of␈α∞sequence␈α∞notation,␈α∞the␈α∞empty␈α∞sequence␈α∞is␈α∞represented␈α∞as:␈α∞ "␈↓α(␈α∞)␈↓".␈α∞ To␈α∂be␈α∞consistent,
␈↓then,␈α
we␈α
will␈α
define␈α␈↓α(␈α
)␈↓␈α
to␈α
be␈α
the␈αsame␈α
as␈α
the␈α
atom␈α
␈↓αNIL␈↓.␈α And␈α
a␈α
notational␈α
point:␈α
 in␈αgraphical
␈↓notation␈α
it␈α
is␈α
often␈α
convenient␈α
to␈α
write



␈↓Thus, for example:

␈↓␈↓ ¬␈␈↓α(A,(B,C),D)␈↓ is:



␈↓α␈↓ ∧λA␈↓ ¬(␈↓ εH    D



␈↓α␈↓ ∧λ␈↓ ¬(   B␈↓ εH   C

␈↓or:

␈↓α␈↓ εOA








␈↓α␈↓ ¬(B    C    NIL     D    NIL


␈↓Finally␈α
in␈α
list-notation,␈α
the␈α
commas␈α
can␈α
be␈α
replaced␈α
by␈α
spaces.

␈↓α␈↓ ¬ e.g. (A,(B,C),D) ≡ (A(B C)D).

␈↓Note:␈α
 the␈α
"dots"␈α
in␈α
dot-notation␈α
are␈α
never␈α
optional.



␈↓␈↓ ε∀␈↓↓Problems ␈↓


␈↓I Which of the following are dotted-pairs.
␈↓␈↓ αh␈↓↓1.␈↓α (X . Y)   ␈↓↓2.␈↓α ((A .(B . C))  ␈↓↓3.␈↓α  A2   ␈↓↓4.␈↓α (X . Y2 . Z)


␈↓II Write the following as binary trees.
␈↓␈↓ αh␈↓↓1.␈↓α  ((A . B).(B . (C . D)))  ␈↓↓2.␈↓α  (A . B).C).E)
␈↓α␈↓ αh␈↓↓3.␈↓α  ((X . NIL).(Y .(Z . NIL)))    ␈↓↓4.␈↓α  (NIL . NIL)


␈↓III Write the following binary trees as Sexprs.

␈↓␈↓ αh␈↓↓1.              2.                       3.
␈↓↓␈↓ αh␈↓α                    A
␈↓α␈↓ αh  A
␈↓α␈↓ αh     B  C                                  A

␈↓α␈↓ αh                         B

␈↓α␈↓ αh                                                 B

␈↓α␈↓ αh                  C  NIL      D   E

␈↓α␈↓ αh                                                    C  NIL



␈↓↓␈↓ αh4.                                5.
␈↓α␈↓ αh    CAR            NIL

␈↓α␈↓ αh                                   CONS        X         Y  NIL


␈↓α␈↓ αh               QUOTE      A  NIL




␈↓IV␈α
Evaluate␈α
the␈α
following

␈↓␈↓ βZ␈↓↓1.␈↓α eq[X;Y]   ␈↓↓2.␈↓α cons[X;Y]   ␈↓↓3.␈↓α car[(X . Y)]   ␈↓↓4.␈↓α car[cons[X;Y]] 

␈↓α␈↓↓5.␈↓α cadr[(X .(Y . NIL))] ␈↓ εH␈↓↓6.␈↓α␈α
cdar[(X␈α
.(Y␈α
.␈α
NIL))]

␈↓α␈↓↓7.␈↓α eq[cdr[(A . B)];cdr[(C . B)]] ␈↓ εH␈↓↓8.␈↓α␈α
atom[cons[(A␈α
.␈α
B);(C␈α
.␈α
D)]]

␈↓α␈↓↓9.␈↓α cons[atom[A];atom[(A . B)]] ␈↓ εH␈↓↓10.␈↓α␈α
eq[atom[ATOM];atom[EQ]]

␈↓α␈↓ βQ␈↓↓11.␈↓α [T → A; T → B]   ␈↓↓12.␈↓α [NIL → A; T → B]   ␈↓↓13.␈↓α [eq[A;B] → 4] 

␈↓α␈↓↓14.␈↓α [atom[X] → atom[X]; T → FOO] ␈↓ εH␈↓↓15.␈↓α␈α
[eq[EQ;X]␈α
→␈α
A;␈α
eq[A;B]␈α
→␈α
B;␈α
T␈α
→␈α
C]

␈↓α␈↓ βj␈↓↓16.␈↓α cons[[eq[A;B] → 1; T → FOO];cons[A;cadr[(A .(B .C))]]] 

␈↓V␈α
 Use␈α
the␈α
following␈α
definition:

␈↓α␈↓ αh  twist[s] <=␈↓ ∧8[atom[s] → s;
␈↓α␈↓ αh␈↓ ∧8 T → cons[twist[cdr[s]];twist[car[s]]]]

␈↓and evaluate:
␈↓␈↓↓1.␈↓α twist[A]   ␈↓↓2.␈↓α twist[(A . B)]   ␈↓↓3.␈↓α twist[((A . B). C)]

␈↓Now try:
␈↓α␈↓ αhfindem[x;y] <=␈↓ ∧8[atom[x] → [eq[x;y] → T; T → NIL];
␈↓α␈↓ αh␈↓ ∧8 T → cons[findem[car[x];y];findem[cdr[x];y]]]

␈↓and evaluate:
␈↓␈↓↓1.␈↓α findem[(A . B);A]   ␈↓↓2.␈↓α findem[(B .(A . C));A]
␈↓α␈↓↓3.␈↓α findem[(B .(A . C));C]   ␈↓↓4.␈↓α findem[(A . B);(A . B)]

␈↓↓␈↓ ∧}Problems involving list-notation

␈↓VI  Translate the following lists into Sexpr dotted-pair notation.
␈↓␈↓ ∧=␈↓↓1.␈↓α (A B C)   ␈↓↓2.␈↓α (A)   ␈↓↓3.␈↓α ((A))   ␈↓↓4.␈↓α (A (B (C))).


␈↓Now go the other way and translate the following sexprs into list notation.
␈↓␈↓ β{␈↓↓5.␈↓α ((A .(B . NIL)).((C . NIL). NIL))   ␈↓↓6.␈↓α (NIL . NIL)
␈↓α␈↓ ∧O␈↓↓7.␈↓α ((CONS .((QUOTE .(A . NIL)). NIL))




␈↓VII  Evaluate the following, writing the results in list notation where possible.
␈↓␈↓ βG␈↓↓1.␈↓α car[(A B)]   ␈↓↓2.␈↓α cdr[(A B)]   ␈↓↓3.␈↓α cons[A;(B C)]   ␈↓↓4.␈↓α cons[A;NIL]
␈↓α␈↓ ¬A␈↓↓5.␈↓α cons[eq[A;A];(A B C)]

␈↓VIII  Use the following defintion:
␈↓α␈↓ αhmatch[k;m] <=␈↓ ∧8[null[k] → NO;
␈↓α␈↓ αh␈↓ ∧8 null[m] → NO;
␈↓α␈↓ αh␈↓ ∧8 eq[car[k];car[m]] → car[k];
␈↓α␈↓ αh␈↓ ∧8 T → match[cdr[k];cdr[m]]]

␈↓and evaluate:
␈↓␈↓↓1.␈↓α match[(X);(X)]   ␈↓↓2.␈↓α match[(A B E);(J O E)]  ␈↓↓3.␈↓α match[(F O O); (BAZ)]

␈↓IX␈α
 Now␈α
write␈α
your␈α
own.

␈↓␈↓↓1.␈↓α␈α
among[x;y]␈α∞<=␈α
...␈α∞:␈α
among␈↓␈α∞is␈α
to␈α
be␈α∞a␈α
predicate;␈α∞␈↓αx␈↓␈α
is␈α∞an␈α
atom;␈α
␈↓αy␈↓␈α∞is␈α
a␈α∞list␈α
of␈α∞atoms.␈α
 ␈↓αamong␈↓␈α∞is␈α
to
␈↓return␈α
␈↓αNIL␈↓␈α
if␈α
␈↓αx␈↓␈α
is␈α
not␈α
found␈α
as␈α
an␈α
element␈α
of␈α
␈↓αy␈↓;␈α
o.w.␈α
 among␈α
is␈α
to␈α
return␈α
␈↓αT␈↓.
␈↓␈↓ αhe.g. ␈↓αamong[A;(A B C)] = among[A;(C D E A)] = T
␈↓α␈↓ αh     among[A1;(A2 B2)] = NIL.

␈↓␈↓↓2.␈↓α␈α
anywhere[x;y]␈α
<=␈α
...␈α:␈α
anywhere␈↓␈α
is␈α
a␈α
predicate;␈α␈↓αx␈↓␈α
is␈α
an␈α
atom;␈α
␈↓αy␈↓␈αis␈α
an␈α
arbitrary␈α
sexpr.␈α
␈↓αanywhere␈↓␈αis␈α
to
␈↓return␈α
␈↓αT␈↓␈α
just␈α
in␈α
the␈α
case␈α
that␈α
␈↓αx␈↓␈α
appears␈α
somewhere␈α
in␈α
␈↓αy␈↓.

␈↓␈↓ αhe.g. ␈↓αanywhere[A;(A B C)] = anywhere[A;((A . B). C)] = T
␈↓α␈↓ αh     anywhere[A;(B C D)] = NIL.

␈↓␈↓ ∧≠␈↓↓I. The Great Mother of All Functions!!! (␈↓αtgmoaf␈↓↓)

␈↓α␈↓ αhtgmoaf[x] <=␈↓ ∧X[atom[x] →␈↓ ελ[eq[x ;T] → T;
␈↓α␈↓ αh␈↓ ∧X␈↓ ελ eq[x;NIL] → NIL;
␈↓α␈↓ αh␈↓ ∧X␈↓ ελ T → TRYAGAINNEXTWEEK];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];QUOTE] → cadr[x];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];CAR] → car[tgmoaf[cadr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];CDR] → cdr[tgmoaf[cadr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];CONS] → cons[tgmoaf[cadr[x]];tgmoaf[caddr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];ATOM] → atom[tgmoaf[cadr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];EQ] → eq[tgmoaf[cadr[x]];tgmoaf[caddr[x]]];
␈↓α␈↓ αh␈↓ ∧X T → TRYAGAINNEXTWEEK]




␈↓Evaluate the following:

␈↓␈↓↓1.␈↓α tgmoaf[T]
␈↓α␈↓↓2.␈↓α tgmoaf[A]
␈↓α␈↓↓3.␈↓α tgmoaf[(CAR(QUOTE(A . B)))]
␈↓α␈↓↓4.␈↓α tgmoaf[(CDR (QUOTE (A B)))]
␈↓α␈↓↓5.␈↓α tgmoaf[(EQ (CAR (QUOTE (A . B)))(QUOTE A))]
␈↓α␈↓↓6.␈↓α tgmoaf[(EQ (CAR (QUOTE (A . B))) A)]
␈↓α␈↓↓7.␈↓α tgmoaf[(ATOM (CAR (QUOTE (A B))))]



␈↓α␈↓ βO␈↓↓II. The Great Mother of All Functions Revisited!!!(␈↓αtgmoafr␈↓↓)

␈↓α␈↓ αhtgmoafr[x] <=␈↓ ∧X[atom[x] →␈↓ ελ[eq[x;T] → T;
␈↓α␈↓ αh␈↓ ∧X␈↓ ελ eq[x;NIL] → NIL;
␈↓α␈↓ αh␈↓ ∧X␈↓ ελ T → TRYAGAINNEXTWEEK];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];QUOTE] → cadr[x];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];CAR] → car[tgmoafr[cadr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];CDR] → cdr[tgmoafr[cadr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];CONS] → cons[tgmoafr[cadr[x]];tgmoafr[caddr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];ATOM] → atom[tgmoafr[cadr[x]]];
␈↓α␈↓ αh␈↓ ∧X eq[car[x];COND] → evcond[cdr[x]];
␈↓α␈↓ αh␈↓ ∧X T → TRYAGAINNEXTWEEK]

␈↓α␈↓ αhevcond[x] <=␈↓ ∧X[tgmoafr[caar[x]] → tgmoafr[cadar[x]];
␈↓α␈↓ αh␈↓ ∧X T → evcond[cdr[x]] ]

␈↓Evaluate the following:

␈↓␈↓↓1.␈↓α tgmoafr[T]
␈↓α␈↓↓2.␈↓α tgmoafr[(CDR (QUOTE (A B)))]
␈↓α␈↓↓3.␈↓α tgmoafr[(EQ (CAR (QUOTE (A . B))) (QUOTE A))]
␈↓α␈↓↓4.␈↓α tgmoafr[(COND((EQ (CAR (QUOTE (A . B)))(QUOTE A))(QUOTE FOO)))]
␈↓α␈↓↓5.␈↓α tgmoafr[(COND((ATOM (QUOTE (A)))(QUOTE FOO))(T(QUOTE BAZ)))]

␈↓␈↓ ¬&␈↓↓Problems involving ␈↓αprog.  ␈↓ 

␈↓Write␈α
␈↓αprog␈↓-versions␈α
of␈α
the␈α
following␈α
functions␈α
(or␈α
predicates).

␈↓␈↓↓1.␈↓α␈α
member[x;y]<=␈α
...␈α
:␈α
x␈↓␈α
is␈α
atomic;␈α
␈↓αy␈↓␈α
is␈α
a␈α
list␈αof␈α
atoms.␈α
 ␈↓αmember␈↓␈α
is␈α
to␈α
return␈α
␈↓αT␈↓␈α
just␈α
in␈α
the␈α
case␈α
that␈α␈↓αx␈↓␈α
is
␈↓one␈α
of␈α
the␈α
elements␈α
in␈α
␈↓αy␈↓.



␈↓␈↓↓2.␈↓␈α
The␈α
factorial␈α
funciion.

␈↓␈↓↓3.␈↓α␈α
 delete[x;y]<=␈α
...␈α
:␈α
x␈↓␈α
is␈α
atomic;␈α
␈↓αy␈↓␈α
is␈α
a␈α
list␈αof␈α
atoms.␈α
 ␈↓αdelete␈↓␈α
is␈α
to␈α
return␈α
a␈α
list␈α
which␈α
looks␈α
like␈α␈↓αy␈↓,
␈↓except␈α
all␈α
occurrences␈α
of␈α
␈↓αx␈↓␈α
have␈α
been␈α
deleted.

␈↓␈↓↓4.␈↓␈α
The␈α
␈↓αappend␈↓␈α
function.

␈↓␈↓↓5.␈↓α␈α
 last[x]<=␈α
...␈α
:␈α
x␈↓␈α
is␈α
a␈α
non-empty␈α
list.␈α
 ␈↓αlast␈↓␈α
is␈α
to␈α
return␈α
the␈α
last␈α
element␈α
in␈α
␈↓αx␈↓.

␈↓␈↓↓6.␈↓␈α
 Now␈α
write␈α
the␈α
Sexpr␈α
translations␈α
of␈α
each␈α
of␈α
your␈α
functions.

␈↓␈↓ ∧{␈↓↓Hacking with ␈↓αeval␈↓↓ and friends.  ␈↓ 

␈↓Assume␈α
that␈α
the␈α
variable,␈α
␈↓αst␈↓,␈α
is␈α
currently␈α
bound␈α
to:
␈↓␈↓ ∧u␈↓α((X . M)(Y . T)(Z .(M N))(T . T)).

␈↓evaluate:

␈↓␈↓↓1.␈↓α assoc[Z;st]
␈↓α␈↓↓2.␈↓α eval[(QUOTE A);st]
␈↓α␈↓↓3.␈↓α apply[CONS;(A B); st]
␈↓α␈↓↓4.␈↓α apply[CAR;((A));st]
␈↓α␈↓↓5.␈↓α apply[CAR;(A);st]